﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace DataStructure
{
    public interface IString : IEnumerable<char>, IEnumerable
    {
        IString StrCopy();
        bool StrEmpty();
        int StrCompare(IString s);
        int StrLength();
        void ClearStr();
        IString Concat(IString s);
        IString SubStr(int pos, int len);
        int Index(IString s, int pos);
        IString Replace(IString s, IString t);
        IString StrInsert(int pos, IString s);
    }

    public class SString : IString
    {
        public char[] data;

        public SString(char[] s)
        {
            this.data = s;
        }

        public SString(SString s)
        {
            Array.Copy(s.data, this.data, s.data.Length);
        }

        public SString(string s)
        {
            data = s.ToArray<char>();
        }

        #region IString Members

        public IString StrCopy()
        {
            IString s = new SString(this);
            return s;
        }

        public bool StrEmpty()
        {
            if (data == null || data.Length == 0)
            {
                return true;
            }
            else
            {
                return false;
            }


        }

        public int StrCompare(IString s)
        {
            SString ss = s as SString;
            for (int i = 0; i < data.Length; i++)
            {
                if (data[i] > ss.data[i])
                {
                    return 1;
                }
                else if (data[i] < ss.data[i])
                {
                    return -1;
                }
            }
            return 0;
        }

        public int StrLength()
        {
            if (data == null)
            {
                return 0;
            }
            else
            {
                return data.Length;
            }
        }

        public void ClearStr()
        {
            data = null;
        }

        public IString Concat(IString s)
        {
            SString ss = s as SString;
            if (ss.StrLength() == 0)
                return this;
            char[] newdata = new char[this.StrLength() + ss.StrLength()];

            Array.Copy(this.data, newdata, this.data.Length);
            Array.Copy(ss.data, 0, newdata, this.data.Length, ss.data.Length);

            return new SString(newdata);
        }

        public IString SubStr(int pos, int len)
        {
            char[] newdata = new char[len];
            Array.Copy(this.data, pos, newdata, 0, len);
            return new SString(newdata);
        }

        public int Index(IString s, int pos)
        {
            SString ss = s as SString;
            return Strings.KMP(new string(this.data, 0, this.data.Length), new string(ss.data, 0, ss.StrLength()), pos);
        }

        public IString Replace(IString s, IString t)
        {
            throw new NotImplementedException();
        }

        public IString StrInsert(int pos, IString s)
        {
            char[] newdata = new char[this.data.Length + s.StrLength()];
            Array.Copy(this.data, 0, newdata, 0, pos);
            SString ss = s as SString;
            Array.Copy(ss.data, 0, newdata, pos, ss.data.Length);
            Array.Copy(this.data, pos, newdata, pos + ss.data.Length, this.data.Length - pos);

            return new SString(newdata);

        }

        #endregion

        #region IEnumerable<char> Members
        class MyClass : IEnumerator<char>, IEnumerator
        {
            int currentIndex = -1;
            char[] data = null;
            #region IEnumerator<char> Members
            public MyClass(char[] s)
            {
                this.data = s;
            }
            public char Current
            {
                get
                {
                    return data[currentIndex];
                }
            }

            #endregion

            #region IDisposable Members

            public void Dispose()
            {
                data = null;
            }

            #endregion

            #region IEnumerator Members

            object IEnumerator.Current
            {
                get { return data[currentIndex]; }
            }

            public bool MoveNext()
            {
                if (currentIndex == this.data.Length - 1)
                {
                    return false;
                }
                else
                {
                    currentIndex++;
                    return true;
                }
            }

            public void Reset()
            {
                this.currentIndex = -1;
            }

            #endregion
        }
        public IEnumerator<char> GetEnumerator()
        {
            return new MyClass(this.data);
        }
        #endregion

        #region IEnumerable Members

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.data.GetEnumerator();
        }

        #endregion

    }

    public class HString
    {

    }

    public class LString
    {

    }

    public class Strings
    {

        public static int MyKMP(string source, string sub, int pos = 0)
        {
            int[] next = Next(sub);
            int i = pos;
            int j = 0;
            while (i < source.Length && j < sub.Length)
            {
                if (j == -1 || source[i] == sub[j])
                {
                    i++; j++;
                }
                else
                {
                    Console.WriteLine("{0}-{1}", j, next[j]);
                    j = next[j];
                }
            }
            if (j >= sub.Length) return i - sub.Length;
            else return -1;
        }

        public static int[] MyNext(string t)
        {
            int[] next = new int[t.Length];
            next[0] = -1;
            int j = 0, k = -1;

            while (j < t.Length)
            {
                if (k == -1 || t[j] == t[k])
                {
                    ++j;
                    ++k;
                    if (j == t.Length)
                        break;
                    //next[j] = k; 
                    //below is improvement
                    if (t[j] != t[k])
                    {
                        next[j] = k;
                    }
                    else
                    {
                        next[j] = next[k];
                    }
                }
                else
                {
                    k = next[k];
                }
            }

            return next;
        }


        
        //des是目标串，pat是模式串，len1和len2是串的长度
        /// <summary>
        /// 　现在不妨假设，当前匹配情况是这样的：S0 …… St St+1 …… St+j  与 P0 P1…… Pj ，
        /// 　现在正在尝试匹配的字符是St+j+1和Pj+1，并且St+j+1 != Pj+1，言外之意就是说St St+1……St+j和P0 P1……Pj是完全匹配的。
        /// 　那么这个时候，S中下一次匹配开始位置应该是什么呢？？按照朴素的模式匹配，下次比较应该从St+1开始，并且令St+1和P0比较，
        /// 　但是在快速模式匹配中并不是这样，快速模式匹配选择St+j+1和Pk+1比较，K是什么呢？
        /// 　K是这样的一个值，使得P0 P1……Pk 和 Pj-k Pj-k+1……Pj完全匹配，不妨设k=next[j]，因此P0 P1……Pk和St+j-k St+j-k+1 ……St+j完全匹配。
        /// 　那么下一次要进行匹配的两个字符应为St+j+1和Pk+1。S和P都没有回溯到下标0在进行比较，这就是KMP之所以快的原因啦。
        /// 　
        /// 现在关键问题来了，这个K怎么能得到呢？如果得到这个K值复杂度高，那这个思路就不好了，其实这个K呢，
        /// 只和模式串P有关系，并且要求m个k，k = next[j]，因此只要算一次存储到next数组中就可以了，并且时间复杂度和m有关系（线性关系）。
        /// 看看具体怎么求next数组的值，即求k。
        /// 用归纳法求next[]：设next(0) = -1，若已知next(j) = k，欲求得next[j+1]。
        /// （1）如果Pk+1 = Pj+1，显然next[j+1] = k+1. 
        ///     如果Pk+1 != Pj+1，则next[j+1] < next[j]，
        ///     于是寻找h < k 使得P0 P1……Ph = Pj-h Pj-h+1……Pj = Pk-h Pk-h+1……Pk。
        ///     也就是说h = next(k);看出来了吧，这是个迭代的过程。（也就是以前的结果对求以后的值有用）
        /// （2）如果不存这样的h，说明P0 P1……Pj+1中没有前后相等的子串，因此next[j+1] =-1.
        /// （3）如果存在这样的h，继续检验Ph和Pj是否相等。知道找到这中相等的情况，或者确定为-1求next[j+1]的过程结束。
        /// </summary>
        public static int KMP(string source, string pattern, int pos = 0)
        {
            int[] next = Next(pattern);
            int p = 0, s = pos;
            while (p < pattern.Length && s < source.Length)
            {
                if (pattern[p] == source[s])
                {
                    p++; s++;
                }
                else
                {
                    if (p == 0)
                    {
                        s++;//若第一个字符就匹配失败，则从des的下一个字符开始
                    }
                    else
                    {
                        p = next[p - 1] + 1;//用失败函数确定pat应回溯到的字符
                    }
                }
            }

            if (p < pattern.Length)//整个过程匹配失败
            {
                return -1;
            }
            return s - pattern.Length;
        }

        //注意返回结果是一个数组next，保存m个k值得地方，即若next[j]=k
        //则str[0]str[1]…str[k] = str[j-k]str[j-k+1]…str[j]
        //这样当des[t+j+1]和pat[j+1]匹配失败时，下一个匹配位置为des[t+j+1]和next[j]+1
        public static int[] Next(string pattern)
        {
            int[] next = new int[pattern.Length];
            next[0] = -1;
            
            for (int j = 1; j < pattern.Length; j++)
            {
                int i = next[j - 1];
                while (pattern[j] != pattern[i + 1] && i >= 0)//迭代的过程
                {
                    i = next[i];
                }
                if (pattern[j] == pattern[i + 1])
                {
                    next[j] = i + 1;
                }
                else
                {
                    next[j] = -1;
                }
            }
            return next;
        }
    }
}
